package com.cango.student.algorithm.leetcode;

/**
 * 对于人民币的面值有1元 5元 10元 20元 50元 100元，下面要求设计一个程序，输入找零的钱，输出找钱方案中最少张数的方案。
 *
 * 贪心算法
 */
public class RMBReturn {

    public static void main(String[] args) {
        int[] p = {100, 50, 20, 10, 5, 1};
        int x = 688;
        int count = 0;

        for (int i = 0; i < p.length; i++) {
            int sum = x / p[i];
            count = count + sum;
            x = x - sum * p[i];

            System.out.println("面额" + p[i] + "用了" + sum);
            System.out.println("还剩" + x + "元");
        }
        System.out.println("用了" + count + "张");
    }
}
